// 时间复杂度: 平均O(n2) 最坏O(n2) 最好O(n2)
// 空间复杂度: O(1)
// 稳定性: 不稳定排序

class SelectionSort {
public:
    static void selectionSort(int *array, int length) {
        for (int i = 0; i < length - 1; ++i) {
            int index = i;
            int minValue = array[i];

            for (int j = i + 1; j < length; ++j) {
                if (array[j] < minValue) {
                    index = j;
                    minValue = array[j];
                }
            }

            if (index != i) {
                int temp = array[i];
                array[i] = array[index];
                array[index] = temp;
            }
        }
    }
};